package com.lishem.carl._05doublepointer;

import com.lishem.common.ListNode;

/**
 * https://leetcode.cn/problems/intersection-of-two-linked-lists/description/
 * <p>
 * 给你两个单链表的头节点headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回null 。
 */
public class _11LetCode160_链表相交 {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pA = headA;
        ListNode pB = headB;
        int countA = 0;
        int countB = 0;
        while (pA != null) {
            pA = pA.next;
            countA++;
        }
        while (pB != null) {
            pB = pB.next;
            countB++;
        }
        ListNode fast, slow;
        int dif;
        if (countA > countB) {
            fast = headA;
            slow = headB;
            dif = countA - countB;
        } else {
            fast = headB;
            slow = headA;
            dif = countB - countA;
        }
        while (dif-- > 0) {
            fast = fast.next;
        }
        while (fast != null && slow != null) {
            if (fast == slow) {
                return fast;
            }
            fast = fast.next;
            slow = slow.next;
        }
        return null;
    }

    public static void main(String[] args) {
        _11LetCode160_链表相交 sol = new _11LetCode160_链表相交();
        ListNode headA = new ListNode(4);
        headA.next = new ListNode(1);
        headA.next.next = new ListNode(8);
        headA.next.next.next = new ListNode(4);
        headA.next.next.next.next = new ListNode(5);
        ListNode headB = new ListNode(5);
        headB.next = new ListNode(6);
        headB.next.next = new ListNode(1);
        headB.next.next = headA.next.next;
        System.out.println(sol.getIntersectionNode(headA, headB).val); // 8

    }
}
